{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 第七十一题 冒泡排序",
   "id": "34898d54fe4a9fc4"
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-03-08T08:20:04.376932Z",
     "start_time": "2025-03-08T08:20:04.344067Z"
    }
   },
   "source": [
    "from Demos.win32cred_demo import target\n",
    "\n",
    "\n",
    "#两两比较，交换，大数沉底\n",
    "def bubble_sort(li):\n",
    "    for i in range(len(li)):\n",
    "        for j in range(len(li)-i-1):  #因为要和j+1那一项进行比较，减i是因为大数沉底了，已经比较好不动了\n",
    "            if li[j]>li[j+1]:\n",
    "                li[j],li[j+1]=li[j+1],li[j]\n",
    "    return li\n",
    "list=[1,5,4,3,2]\n",
    "print(bubble_sort(list))"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n"
     ]
    }
   ],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 第七十二题 选择排序",
   "id": "a86776451503b71a"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T08:28:00.440826Z",
     "start_time": "2025-03-08T08:28:00.418140Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def selection_sort(li):\n",
    "    for i in range(len(li)):\n",
    "        min_index=i\n",
    "        for j in range(i,len(li)):\n",
    "            if li[min_index]>li[j]:\n",
    "                min_index=j\n",
    "        li[min_index],li[i]=li[i],li[min_index]\n",
    "    return li\n",
    "\n",
    "list=[5,2,3,89,1]\n",
    "print(selection_sort(list))"
   ],
   "id": "43423e45940873d8",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 89]\n"
     ]
    }
   ],
   "execution_count": 2
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 第七十三题 插入排序",
   "id": "31fe4dcdc8ca2a15"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T08:37:48.408183Z",
     "start_time": "2025-03-08T08:37:48.387534Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#这个再看看！\n",
    "def insert_sort(li):\n",
    "    for i in range(1,len(li)):\n",
    "        j=i-1  #已排序列最后一个\n",
    "        key=li[i]\n",
    "        while j>=0:\n",
    "            if li[j]>key:\n",
    "                li[j+1]=li[j]\n",
    "                li[j]=key\n",
    "            j-=1\n",
    "    return li\n",
    "list=[5,78,23,1,2]\n",
    "print(insert_sort(list))\n",
    "        "
   ],
   "id": "1918c7104f7fcf99",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 5, 23, 78]\n"
     ]
    }
   ],
   "execution_count": 3
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十四题 字符删除\n",
    "    给定两个字符串str和sub，从str中完全删除在sub中存在的字符"
   ],
   "id": "f029b0cdcef06311"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T08:40:53.679819Z",
     "start_time": "2025-03-09T08:40:53.637033Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(str,sub):\n",
    "    s=set(sub)  #如果有重复遍历起来会很浪费，变成集合去重\n",
    "    ans=''\n",
    "    for i in str:  \n",
    "        if i not in s:   #选取in的话还要删除替换啊很麻烦，not in再加到空字符串中就简单多了\n",
    "            ans+=i\n",
    "    return ans\n",
    "print(func('Thank you!','you'))"
   ],
   "id": "2c2b2f0e1ff60a1f",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Thank !\n"
     ]
    }
   ],
   "execution_count": 4
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十五题 目标移动\n",
    "    给定一个数组nums和目标值target。将target元素移动到数组前面，其他元素相对顺序不变"
   ],
   "id": "dfde01f8cc3c40f9"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T08:55:48.940392Z",
     "start_time": "2025-03-09T08:55:48.931140Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(nums,target):\n",
    "    count=0  #target元素个数\n",
    "    left=len(nums)-1\n",
    "    right=len(nums)-1\n",
    "    \n",
    "    while left>=0:\n",
    "        if nums[left] !=target:\n",
    "            nums[right]=nums[left]\n",
    "            right-=1\n",
    "        else:\n",
    "            count+=1\n",
    "        left-=1\n",
    "    for i in range(count):\n",
    "        nums[i]=target\n",
    "list=[1,2,1,4,1]\n",
    "target=1\n",
    "func(list,target)\n",
    "print(list)\n",
    "    "
   ],
   "id": "f631a23817b8c6f0",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 2, 4]\n"
     ]
    }
   ],
   "execution_count": 7
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十六题 柠檬水找零\n",
    "    在柠檬水摊上，每一杯柠檬水的售价是5美元。顾客排队购买你的产品，（按账单bills支付的顺序）一次购买一杯。   \n",
    "    每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付5美元。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回true，否则返回false\n",
    "    "
   ],
   "id": "8705ce52d2cd8833"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T09:07:47.976065Z",
     "start_time": "2025-03-09T09:07:47.964924Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#贪心算法\n",
    "def func(nums):\n",
    "    five=0\n",
    "    ten=0\n",
    "    for i in nums:\n",
    "        #5\n",
    "        if i==5:\n",
    "            five+=1\n",
    "        elif i==10:\n",
    "            if five>0:\n",
    "                five-=1\n",
    "                ten+=1\n",
    "            else :\n",
    "                return False\n",
    "        else: \n",
    "            if five>0 and ten >0:\n",
    "                five-=1\n",
    "                ten-=1\n",
    "            elif five>=3:\n",
    "                five-=3\n",
    "            else :\n",
    "                return False\n",
    "    return True\n",
    "print(func([5,5,5,10,20]))\n",
    "print(func([5,5,10,10,20]))"
   ],
   "id": "7062c7a689a832e0",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十七题 尾部的零\n",
    "    给定一个整数n，计算出n！中尾部的0的个数"
   ],
   "id": "6f419a8baa5320c5"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T09:16:57.916678Z",
     "start_time": "2025-03-09T09:16:57.907019Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import math\n",
    "#尾部0  -->5的倍数有多少\n",
    "def func(n):\n",
    "    count=0\n",
    "    for i in range(5,n+1,5):\n",
    "        while i%5==0:\n",
    "            i//=5\n",
    "            count+=1\n",
    "    return count\n",
    "print(func(11))\n",
    "print(math.factorial(11))"
   ],
   "id": "b530b5e4840fbe23",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "39916800\n"
     ]
    }
   ],
   "execution_count": 9
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十八题 统计数字\n",
    "    给定一个数字k,计算k在0到n中出现的次数"
   ],
   "id": "c2499aedec897335"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T09:20:51.025826Z",
     "start_time": "2025-03-09T09:20:51.013424Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(k,n):\n",
    "    count=0\n",
    "    for i in range(0,n+1):\n",
    "        time=str(i).count(str(k))\n",
    "        count+=time\n",
    "    return count\n",
    "print(func(1,11))"
   ],
   "id": "4a39b8f39db33165",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "execution_count": 10
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十九题 合并排序数组\n",
    "    将有序数组A和B合并，要求合并后的新数组也要有序"
   ],
   "id": "2060de8af2dc3f2a"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T09:30:40.053220Z",
     "start_time": "2025-03-09T09:30:40.041826Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(A,B):\n",
    "    i,j=0,0\n",
    "    c=[]\n",
    "    while i<len(A) and j<len(B):\n",
    "        if A[i]<B[j]:\n",
    "            c.append(A[i])\n",
    "            i+=1\n",
    "        else:\n",
    "            c.append(B[j])\n",
    "            j+=1\n",
    "    #其中一个数组被遍历完了\n",
    "    while i<len(A):\n",
    "        c.append(A[i])\n",
    "        i+=1\n",
    "    while j<len(B):\n",
    "        c.append(B[j])\n",
    "        j+=1\n",
    "    return c\n",
    "print(func([1,4,9],[2,3,11]))\n"
   ],
   "id": "3a21bb98f06aaafe",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 9, 11]\n"
     ]
    }
   ],
   "execution_count": 12
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第八十题 插入5\n",
    "    给定一个数字，在数字的任意位置插入一个5，使得插入后的这个数字最大"
   ],
   "id": "755c62794cf2ed91"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T09:52:45.780600Z",
     "start_time": "2025-03-09T09:52:45.767684Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#不是很懂，再看看\n",
    "def func(a):\n",
    "    string=''\n",
    "    ans=0\n",
    "    n=0\n",
    "    flag=False\n",
    "    if a>=0:\n",
    "        string=str(a)\n",
    "        n=len(string)\n",
    "        for i in range(n):\n",
    "            if (ord(string[i])-ord('0'))<5 and flag==False:\n",
    "                ans=ans*10+5\n",
    "                flag=True\n",
    "            ans=ans*10+ord(string[i])-ord('0')\n",
    "        if flag==False:\n",
    "            ans=ans*10+5\n",
    "    else:\n",
    "        a=-a\n",
    "        string=str(a)\n",
    "        n=len(string)\n",
    "        for i in range(n):\n",
    "            if ord(string[i])-ord('0')>5 and flag==False:\n",
    "                ans=ans*10+5\n",
    "            ans=-ans\n",
    "    return ans\n",
    "print(func(6234))"
   ],
   "id": "3883aca9c2e370a9",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "65234\n"
     ]
    }
   ],
   "execution_count": 15
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第八十一题 字符串置换\n",
    "    给定两个字符串，判断其中一个字符串是否为另一个字符串的置换\n",
    "    置换的意思是，通过改变顺序可以使得两个字符串相等"
   ],
   "id": "e87db703d51c7001"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T09:55:28.558074Z",
     "start_time": "2025-03-09T09:55:28.545875Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(A,B):\n",
    "    A=sorted(A)\n",
    "    B=sorted(B)\n",
    "    return A==B\n",
    "print(func('abc','cba'))"
   ],
   "id": "aeba9f71b42559d1",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "execution_count": 16
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
